//
//  MyTool.swift
//  数据结构与算法
//
//  Created by 深圳链上时代 on 2020/12/9.
//

import Foundation

/// 十进制转二进制
/// - Parameter decimal: 十进制数字
/// - Returns: 二进制数字
func decimalToBinary(_ decimal: Int8) -> String {
    if decimal < 0 {
        let reverseNum = ((decimal * -1) ^ Int8.max) + 1
        return decimalToBinary(reverseNum)
    }
    var sum = ""
    var m = decimal
    while m != 0 {
        sum += "\(m & 1)"
        m >>= 1
    }
    return String(sum.reversed())
}

/// 计算大于1的正整数之平方根
/// - Parameters:
///   - n: 待求的数
///   - deltaThreshold: 误差的阈值
///   - maxTry: 二分查找的最大次数
/// - Returns: 平方根的解
func getSquareRoot(n :Int, deltaThreshold: Double, maxTry: Int) -> Double? {
    if n <= 1 {
        return nil;
    }
    
    var min = 1.0, max = Double(n)
    var middle, square, delta: Double
    for _ in 0..<maxTry {
        middle = min + (max - min) / 2
        square = middle * middle
        delta = fabs((square - Double(n)) / Double(n))
        if delta <= deltaThreshold {
            return middle
        } else {
            if square > Double(n) {
                max = middle
            } else {
                min = middle
            }
        }
    }
    
    return nil;
}


/// 使用函数的递归（嵌套）调用，找出所有可能的奖赏组合
/// - Parameters:
///   - totalReward: 奖赏总金额
///   - result: 保存当前的解
func getBonusCombination(totalReward: Int, result: [Int] = []) {
    let rewards = [1, 2, 5, 10]
    if totalReward == 0 {
        print(result)
    } else if totalReward < 0 {
        return
    } else {
        for reward in rewards {
            var newResult = result
            newResult.append(reward)
            getBonusCombination(totalReward: totalReward - reward, result: newResult)
        }
    }
}

/// 一个整数可以被分解为多个整数的乘积，例如，6 可以分解为 2x3。请使用递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）。例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……
func getFactorization(number: Int, result: [Int] = []) {
    if number == 1 {
        var newResult = result
        if !newResult.contains(1) {
            print(newResult.map { "\($0)" }.joined(separator: "x"))
            newResult.append(1)
        }
        print(newResult.map { "\($0)" }.joined(separator: "x"))
    } else if number <= 1 {
        return
    } else {
        for i in 1...number {
            if i == 1 && result.contains(1) {
                continue
            }
            if number % i == 0 {
                var newResult = result
                newResult.append(i)
                getFactorization(number: number / i, result: newResult)
            }
        }
    }
}

/// 使用函数的递归（嵌套）调用，实现归并排序（从小到大）
/// - Parameter toSort: 等待排序的数组
/// - Returns: 排序后的数组
func mergeSort(toSort: [Int]) -> [Int] {
    if toSort.count == 1 {
        return toSort
    }
    
    // 将数组分成两段
    let mid = toSort.count / 2
    var leftSort = Array(toSort.prefix(mid))
    var rightSort = Array(toSort.suffix(from: mid))
    
    // 嵌套调用，对两半分别进行排序
    leftSort = mergeSort(toSort: leftSort)
    rightSort = mergeSort(toSort: rightSort)
    
    // 合并排序后的两半
    return merge(leftSort, rightSort)
}

/// 合并两个已经排序完毕的数组（从小到大）
/// - Parameters:
///   - leftSort: 第一个数组
///   - rightSort: 第二个数组
/// - Returns: 合并后的数组
func merge(_ leftSort: [Int], _ rightSort: [Int]) -> [Int] {
    var merged = [Int]()
    var m = 0, a = 0, b = 0
    while a < leftSort.count && b < rightSort.count {
        if leftSort[a] <= rightSort[b] {
            merged.append(leftSort[a])
            a += 1
        } else {
            merged.append(rightSort[b])
            b += 1
        }
        m += 1
    }
    
    // 将剩余的数据添加到数组
    merged.append(contentsOf: leftSort.suffix(from: a))
    merged.append(contentsOf: rightSort.suffix(from: b))
    
    return merged
}

/// 假设有一个 4 位字母密码，每位密码是 a～e 之间的小写字母。你能否编写一段代码，来暴力破解该密码？（提示：根据可重复排列的规律，生成所有可能的 4 位密码。）
func getPassword(n :Int, result: String = "") {
    let arr = ["a", "b", "c", "d", "e"]
    if n == 0 {
        print(result)
    } else {
        for letter in arr {
            getPassword(n: n - 1, result: result + letter)
        }
    }
}

/// 使用状态转移方程，计算两个字符串之间的编辑距离
func getStrDistance(a: String, b: String) -> Int {
    /**
     我们假设字符数组 A[]和 B[]分别表示字符串 A 和 B，A[i]表示字符串 A 中第 i 个位置的字符，B[i]表示字符串 B 中第 i 个位置的字符。二维数组 d[,]表示刚刚用于推导的二维表格，而 d[i,j]表示这张表格中第 i 行、第 j 列求得的最终编辑距离。函数 r(i, j) 表示替换时产生的编辑距离。如果 A[i]和 B[j]相同，函数的返回值为 0，否则返回值为 1。
     
     有了这些定义，下面我们用迭代来表达上述的推导过程。
     
     如果 i 为 0，且 j 也为 0，那么 d[i, j]为 0。
     如果 i 为 0，且 j 大于 0，那么 d[i, j]为 j。
     如果 i 大于 0，且 j 为 0，那么 d[i, j]为 i。
     如果 i 大于 0，且 j 大于 0，那么 d[i, j]=min(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + r(i, j))。这里面最关键的一步是 d[i, j]=min(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + r(i, j))。
     */
    
    var d = [[Int]](repeating: [Int](repeating: -1, count: b.count + 1), count: a.count + 1)
    // 如果i为0，且j大于等于0，那么d[i, j]为j
    for j in 0...b.count {
        d[0][j] = j
    }
    // 如果j为0，且i大于等于0，那么d[i, j]为i
    for i in 0...a.count {
        d[i][0] = i
    }
    // i 和 j 都是从 0 开始，所以我计算的 d[i+1, j+1]，而不是 d[i, j]。而 d[i+1, j+1] = min(d[i, j+1] + 1, d[i+1, j] + 1, d[i, j] + r(i, j)。
    // 实现状态转移方程
    for i in 0..<a.count {
        for j in 0..<b.count {
            var r = 0
            if a[a.index(a.startIndex, offsetBy: i)] != b[b.index(b.startIndex, offsetBy: j)] {
                r = 1
            }
            let minDistance = min(d[i][j + 1] + 1, d[i + 1][j] + 1, d[i][j] + r)
            d[i + 1][j + 1] = minDistance
        }
    }
    return d[a.count][b.count]
}

/// 给定总金额和可能的钱币面额，能否找出钱币数量最少的奖赏方式(假设这里我们有三种面额的钱币，2 元、3 元和 7 元。)
func getMoneyPlan(totalMoney: Int, moneyTypes: [Int]) -> Int {
    var c = [Int](repeating: 0, count: totalMoney + 1)
    for i in 1...totalMoney {
        var min = totalMoney
        var temp = min
        for j in moneyTypes {
            let diff = i - j
            if diff >= 0 {
                temp = c[diff] + 1
            } else {
                temp = totalMoney
            }
            if min > temp {
                min = temp
            }
        }
        c[i] = min
    }
    return c[totalMoney]
}

/// 使用栈来实现深度优先搜索
func dfsByStack(root: TreeNode) {
    // 初始化栈
    var stack = Stack<TreeNode>()
    // 根节点入栈
    stack.push(element: root)
    // 只要栈有数据就一直遍历下去
    while !stack.isEmpty() {
        // 弹出栈顶节点
        let node = stack.pop()
        if node?.sons.count == 0 {
            // 没有子节点，即为叶子节点，打印
            print("\(String(describing: node?.prefix ?? ""))\(String(describing: node!.label))：\(String(describing: node!.explanation ?? ""))")
        } else {
            // 非叶子节点，遍历每个子节点
            // 注意，这里使用了一个临时的栈stackTemp
            // 这样做是为了保持遍历的顺序，和递归遍历的顺序是一致的
            // 如果不要求一致，可以直接压入stack
            var stackTemp = Stack<TreeNode>()
            node?.sons.forEach { (key: Character, value: TreeNode) in
                stackTemp.push(element: value)
            }
            while !stackTemp.isEmpty() {
                stack.push(element: stackTemp.pop()!)
            }
        }
    }
}
